package com.jinan.algorithm.dynamicProgramming;

/**
 * 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
 * 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。
 * 开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），
 * 取到的数字将会从数组中移除（数组长度减 1 ）。
 * 玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
 * 如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
 */
public class PredictTheWinner {
    public static void main(String[] args) {
        System.out.println(PredictTheWinner(new int[]{1,5,2}));
        System.out.println(gap(new int[]{1,5,2}, 0, 2));
    }
//    递归
    public static int gap(int[] nums, int i, int j){
        if(i == j) return nums[i];
        return Math.max(nums[i] - gap(nums, i + 1, j), nums[j] - gap(nums, i, j - 1));
    }
    public static boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        if(n <= 1) return true;
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(i == j){
                    dp[i][j] = nums[i];
                }else{
                    dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1] >= 0;
    }
}
